package com.hqq.leetcode.dp;

/**
 * PaintFence 栅栏染色
 * Description:
 * There is a fence with n posts, each post can be painted with one of the k colors.
 * You have to paint all the posts such that no more than two adjacent fence posts have the same color.
 * Return the total number of ways you can paint the fence.
 * Input:
 * n = 3,k = 2;
 * Output:
 * 6
 * Analysis:
 * -------post 1   post 2  post 3
 * way1    0         0       1
 * way2    0         1       0
 * way3    0         1       1
 * way4    1         0       0
 * way5    1         0       1
 * way6    1         1       0
 * TIP:
 * 在染一个柱子的时候, 要考虑是否和上一个柱子颜色相同.
 * <p>
 * 如果和上一个相同的话那么上一个有多少种和上上次不同的染色方案, 那么当前柱子也有多少种染色方案.
 * <p>
 * 如果和上一个不同的话那么染色方案就为(k-1)*(之前总共多少染色方案).
 * <p>
 * Created by heqianqian on 2017/9/15.
 */
public class PaintFence {

    public static void main(String[] args) {
        PaintFence pf = new PaintFence();
        int result = pf.numWays(3, 2);
        System.out.println(result);
    }

    /*
     * @param n: non-negative integer, n posts
     * @param k: non-negative integer, k colors
     * @return: an integer, the total number of ways
     */
    public int numWays(int n, int k) {
        // write your code here
        if (n == 0) {
            return 0;
        }
        int same = 0, diff = k;
        for (int i = 2; i <= n; i++) {
            int t = diff;
            diff = (same + diff) * (k - 1);
            same = t;
        }
        return same + diff;
    }
}
